/*
 * @Author: scl
 * @Date: 2023-09-02 14:49:08
 * @LastEditTime: 2023-09-02 16:37:56
 * @Description: file content
 */
/*
 * @lc app=leetcode.cn id=64 lang=typescript
 *
 * [64] 最小路径和
 *
 * https://leetcode.cn/problems/minimum-path-sum/description/
 *
 * algorithms
 * Medium (69.65%)
 * Likes:    1563
 * Dislikes: 0
 * Total Accepted:    511K
 * Total Submissions: 733.7K
 * Testcase Example:  '[[1,3,1],[1,5,1],[4,2,1]]'
 *
 * 给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
 * 
 * 说明：每次只能向下或者向右移动一步。
 * 
 * 
 * 
 * 示例 1：
 * 
 * 
 * 输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
 * 输出：7
 * 解释：因为路径 1→3→1→1→1 的总和最小。
 * 
 * 
 * 示例 2：
 * 
 * 
 * 输入：grid = [[1,2,3],[4,5,6]]
 * 输出：12
 * 
 * 
 * 
 * 
 * 提示：
 * 
 * 
 * m == grid.length
 * n == grid[i].length
 * 1 <= m, n <= 200
 * 0 <= grid[i][j] <= 200
 * 
 * 
 */

// @lc code=start
function minPathSum(grid: number[][]): number {
    const row=grid.length,col=grid[0].length,dp=new Array(row).fill(0).map(x=>new Array(col))
    for(let i=0;i<row;i++){
        if(grid[i-1]!=undefined)dp[i][0]=dp[i-1][0]+grid[i][0]
        else dp[i][0]=grid[i][0]
    }
    for(let i=1;i<col;i++)dp[0][i]=dp[0][i-1]+grid[0][i]
    for(let i=1;i<row;i++){
        for(let j=1;j<col;j++){
            if(dp[i-1][j]>dp[i][j-1])dp[i][j]=dp[i][j-1]+grid[i][j]
            else dp[i][j]=dp[i-1][j]+grid[i][j]
        }
    }
    return dp[row-1][col-1]
};
// @lc code=end

